
\subsection{Problem 3}

Mandatory (4): First, create a project containing the files contained in the insertion\_sort folder of the task specification. Now complete the function main.c:run(), executing insertion sort a few times, with array size 32 and different input data. Measure the minimum and maximum time needed to execute the sort function.
\\
Q: What were the results of the measurement? How many test sets do you need to cover all possible execution path?
\\
\\
\textbf{Solution:}
\\
\\
With \textit{aiT} we measured a WCET of 45941 cycles for the \texttt{insertion sort} function with an array size of 32. 
With help of the debugger tool we measured the following minimum and maximum execution times for 2 different preordered input sets, as shown in Table~\ref{tab:insertion}.

\begin{table}
\centering
	\begin{tabular}[!htpb]{|c|c|c|c|c|} 
		\hline
		input	& start time	& end time & $\Delta t$ & cycles \\
		\hline
		\hline
		descending ordered	& 124999994 & 124988230 & 11764 & 47059 \\
		ascending ordered	& 124999994 & 124998755 & 1239   & 4959 \\
		\hline
	\end{tabular} 
	\caption{Results for \texttt{insertion sort} with 32-bit input data array \label{tab:insertion}}
\end{table} 

\noindent As it can be seen in Table~\ref{tab:insertion}, the real execution time does depend on the input data. There
are 3 possible input test sets for the execution of a sort algorithm, 2 presorted sequences (ascending and descending) 
and a random sequence. To cover all execution paths leading to the WCET you only need a descending presorted sequence.